package cn.lbl.face.leetCode;


import java.util.Arrays;

/*
nums = [1,2,3,4] ,4,    1,5
1, 3, 6, 10, 2, 5, 9, 3, 7, 4
 */
public class 子数组和排序后的区间和 {
    public static int rangeSum(int[] nums, int n, int left, int right) {
        final int MODULO=1000000007;
        int sumsLength=n * (n + 1) / 2;
        int[] sums = new int[sumsLength];
        int index=0;
        int sum=0;
        for (int i = 0; i <n ; i++) {
            for (int j = i; j <n ; j++) {
                sum+=nums[j];
                sums[index++]=sum;
            }
            sum=0;
        }
        Arrays.sort(sums);
        for (int i = left-1; i <right ; i++) {
            sum=(sum+sums[i])%MODULO;
        }
        return sum;
    }

    public static void main(String[] args) {
        int sum = rangeSum(new int[]{1, 2, 3, 4}, 4, 1, 5);
        System.out.println(sum);
    }


}
